import java.util.ArrayList;
import java.util.List;

public class demo {


    public class BinaryTree {
        static class TreeNode{
            public char val;
            public TreeNode right;
            public TreeNode left;

            public TreeNode(char val) {
                this.val = val;
            }
        }

        public TreeNode createTree(){
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }
        public void preOrder(TreeNode root){
            if (root == null){
                return;
            }
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
        public List<TreeNode> preOrder1(TreeNode root){
            List<TreeNode> ret = new ArrayList<>();
            if (root == null){
                return ret;
            }
            ret.add(root);
            List<TreeNode> LeftTree = preOrder1(root.left);
            ret.addAll(LeftTree);
            List<TreeNode> RightTree = preOrder1(root.right);
            ret.addAll(RightTree);
            return ret;
        }


        public void inOrder(TreeNode root){
            if (root == null){
                return;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
        public List<TreeNode> inOrder1(TreeNode root){
            List<TreeNode> ret = new ArrayList<>();
            if (root == null){
                return ret;
            }
            List<TreeNode> LeftTree = inOrder1(root.left);
            ret.addAll(LeftTree);
            ret.add(root);

            List<TreeNode> RightTree = inOrder1(root.right);
            ret.addAll(RightTree);
            return ret;
        }

        public void postOrder(TreeNode root){
            if (root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
        public List<TreeNode> postOrder1(TreeNode root){
            List<TreeNode> ret = new ArrayList<>();
            if (root == null){
                return ret;
            }
            List<TreeNode> LeftTree = postOrder1(root.left);
            ret.addAll(LeftTree);
            List<TreeNode> RightTree = postOrder1(root.right);
            ret.addAll(RightTree);
            ret.add(root);

            return ret;
        }

        //获取树中结点的个数
        //遍历的思路
        public int size = 0;
        public void nodeSize(TreeNode root){
            if (root == null){
                return;
            }
            size++;
            nodeSize(root.left);
            nodeSize(root.right);
        }
        //子树的思路
        public int nodeSize1(TreeNode root){
            if (root == null){
                return 0;
            }
            return nodeSize1(root.left) + nodeSize1(root.right) + 1;
        }

        //获取叶子结点的个数
        //遍历的思路
        public int leafSize = 0;
        public void getLeafSize(TreeNode root){
            if (root == null){
                return ;
            }
            if (root.left == null&& root.right==null){
                leafSize++;
            }
            getLeafSize(root.left);
            getLeafSize(root.right);
        }
        //子问题的思路
        public int  getLeafSize1(TreeNode root){
            if (root == null){
                return 0;
            }
            if (root.left == null&&root.right == null){
                return 1;
            }
            return getLeafSize1(root.left) + getLeafSize1(root.right);
        }

        //求第k层节点个数
        public int getKLevelNodeCount(TreeNode root,int k){
            if (root == null){
                return 0;
            }
            if (k == 1){
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }

        //求这棵树的高度
        public int getHeight(TreeNode root){
            if (root == null){
                return 0;
            }
            int leftHight = getHeight(root.left);
            int rightHight = getHeight(root.right);
            return leftHight > rightHight ? leftHight +1 : rightHight +1;
        }


    }

}
